import java.util.*;

/**
 * @author lijing
 * @e-mail 1413979079@qq.com
 * @date 2020-03-13 10:49
 * @description 多数元素
 */
public class Solution {
    // 哈希表
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                int v = map.get(num) + 1;
                if (v > nums.length >> 1) {
                    return num;
                }
                map.put(num, v);
            } else {
                map.put(num, 1);
            }
        }
        return nums[0];
    }

    // 排序
    public int majorityElement2(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length >> 1];
    }

    // 摩尔投票法
    public int majorityElement3(int[] nums) {
        int res = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != res) {
                count--;
            } else {
                count++;
            }
            if (count == 0) {
                res = nums[i];
                count = 1;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int res = s.majorityElement3(new int[]{3, 2, 3});
        System.out.println(res);
    }
}
